package com.example.dynamicprogramming42;

/**
 * @description 回溯算法,莱文斯坦距离
 * 莱文斯坦距离的大小，表示两个字符串差异的大小
 * @auther lijiewei
 * @date 2022/5/16 16:26
 */
public class LwstFlashBack {

    private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    //最少编辑次数
    private int minDist = Integer.MAX_VALUE;

    public int getLwst() {
        lwstBt(0, 0, 0);
        return minDist;
    }

    /**
     * 莱文斯坦距离
     * 莱文斯坦距离的大小，表示两个字符串差异的大小
     * @param i 数组a的指针
     * @param j 数组b的指针
     * @param edist 还未处理a[i]和b[j]时，已经执行的编辑操作的次数
     * @return
     * @author lijiewei
     * @date   2022/5/16 20:18
     */
    public void lwstBt(int i, int j, int edist) {
        if (i==n || j==m) {
            if (i<n) {
                edist += (n-i);
            }
            if (j<m) {
                edist += (m-j);
            }
            if (edist < minDist) {
                minDist = edist;
            }
            return;
        }
        //两个字符匹配
        if (a[i] == b[j]) {
            lwstBt(i+1, j+1, edist);
        } else {
            //两个字符不匹配
            //删除a[i]或者b[j]前添加一个字符
            lwstBt(i+1, j, edist+1);
            //删除b[j]或者a[i]前添加一个字符
            lwstBt(i, j+1, edist+1);
            //将a[i]和b[j]替换为相同字符
            lwstBt(i+1, j+1, edist+1);
        }
    }
}
